Thực đơn
Lý_thuyết_mã_hóa
Mục đích của lý thuyết Mã hóa trên kênh truyền (channel encoding theory) là tìm những mã có thể truyền thông nhanh chóng, chứa đựng nhiều mã ký (code word) hợp lệ và có thể sửa lỗi (error correction) hoặc ít nhất phát hiện các lỗi xảy ra (error detection). Các mục đích trên không phụ thuộc vào nhau, và mỗi loại mã có công dụng tối ưu cho một ứng dụng riêng biệt. Những đặc tính mà mỗi loại mã này cần còn tuỳ thuộc nhiều vào xác suất lỗi xảy ra trong quá trình truyền thông. Đối với một đĩa CD thông thường, lỗi trong âm thanh xảy ra chủ yếu là do bụi và những vết xước trên mặt đĩa. Vì thế, các mã được lồng vào với nhau. Dữ liệu được phân bổ trên toàn bộ mặt đĩa. Tuy không được tốt cho lắm, song một mã tái diễn đơn giản có thể được dùng làm một ví dụ dễ hiểu. Chẳng hạn, chúng ta lấy một khối số liệu bit (đại diện cho âm thanh) và truyền gửi chúng ba lần liền. Bên máy thu, chúng ta kiểm tra cả ba phần lặp lại ở trên, từng bit từng bit một, rồi lấy cái nào có số bầu cao nhất. Điểm trái khoáy ở đây là, chúng ta không chỉ truyền gửi các bit theo thứ tự. Chúng ta lồng nó vào với nhau. Khối dữ liệu này, trước tiên, được chia ra làm 4 khối nhỏ. Sau đó chúng ta gửi một bit ở khối đầu tiên, tiếp theo một bit ở khối thứ hai v.v tuần tự qua các khối. Việc này được lặp đi lặp lại ba lần để phân bổ số liệu ra trên bề mặt đĩa. Trong ngữ cảnh của mã tái diễn đơn giản ở trên, việc làm này hình như không được hiệu quả cho lắm. Song hiện nay có những mã có hiệu ứng cao, rất phù hợp với việc sửa lỗi xảy ra đột ngột do một vết xước hay một vết bụi, khi dùng kỹ thuật lồng số liệu nói trên.
Mỗi mã thường chỉ thích hợp cho một ứng dụng nhất định. Viễn thông trong vũ trụ (deep space) bị giới hạn bởi nhiễu nhiệt (thermal noise) trong thiết bị thu. Hiện trạng này không xảy ra một cách đột phát bất thường, song xảy ra theo một chu trình tiếp diễn. Tương tự như vậy, modem với dải tần hẹp bị hạn chế vì nhiễu âm tồn tại trong mạng lưới điện thoại. Những nhiễu âm này có thể được biểu hiện rõ hơn bằng một mô hình âm tạp tiếp diễn. Điện thoại di động "Cell phones" hay có vấn đề do sự suy sóng nhanh chóng xảy ra. Tần số cao được dùng có thể gây ra sự suy sóng tín hiệu một cách nhanh chóng (rapid fading), ngay cả khi máy nhận chỉ dời chỗ vài phân Anh (inches) 1. Một lần nữa, người ta hiện đã có một loại thuộc hạng Mã hóa trên kênh truyền được thiết kế để đối đầu với tình trạng suy sóng.
Từ "Lý thuyết mã hóa đại số" ám chỉ để một chi nhánh của lý thuyết mã hóa trên kênh truyền, trong đó đặc tính của mã được biểu hiện bằng các đại số và dựa vào đó mà nghiên cứu sâu hơn.
Lý thuyết mã hóa đại số được chia ra làm hai loại mã chính
Chúng phân tích ba đặc tính sau của mã—nói chung là:
Mã khối tuyến tính mang tính năng tuyến tính (linearity), chẳng hạn tổng của hai mã ký nào đấy lại chính là một mã ký; và chúng được ứng dụng vào các bit của nguồn trên từng khối một; cái tên mã khối tuyến tính là vì vậy (linear block codes). Có những khối mã bất tuyến tính, song khó mà chứng minh được rằng một mã nào đó là một mã tốt nếu mã ấy không có đặc tính này.
Bất cứ mã khối tuyến tính nào cũng được đại diện là ( n , m , d m i n ) {\displaystyle (n,m,d_{min})} , trong đó
Có nhiều loại mã khối tuyến tính, như
Mã khối được gắn liền với bài toán "đóng gói đồng xu" là bài toán gây một số chú ý trong nhiều năm qua. Trên bề diện hai chiều, chúng ta có thể hình dung được vấn đề một cách dễ dàng. Lấy một nắm đồng xu, để nằm trên mặt bàn, rồi dồn chúng lại gần với nhau. Kết quả cho chúng ta một mẫu hình lục giác tương tự như hình tổ ong. Các mã khối còn dựa vào nhiều chiều khác nữa, không dễ gì mà hình dung được. Mã Golay 2 có hiệu ứng cao, dùng trong truyền thông qua khoảng không vũ trụ, sử dụng những 24 chiều. Nếu được dùng là mã nhị phân (thường thấy), các chiều ám chỉ đến chiều dài của mã ký như đã định nghĩa ở trên.
Lý thuyết về mã sử dụng mô hình hình cầu với số chiều "N". Lấy ví dụ, bao nhiêu đồng xu phải cần để phủ kín một mặt bàn, hay trong khoảng không 3 chiều, bao nhiêu hòn bi phải cần để nhồi kín một hình cầu. Những cân nhắc khác bao gồm việc chọn lựa mã. Lấy ví dụ, do nhồi nhữmg hình lục lăng vào trong một cái hộp hình chữ nhật, chúng ta để lại những khoảng trống ở các góc. Khi các chiều của hộp được tăng lên, tỷ lệ phần trăm so sánh của các khoảng trống nhỏ đi, cho đến một cỡ nào đấy, những phần nhồi chiếm hết các khoảng không và mã này được gọi mã hoàn hảo. Số mã kiểu này tương đối hiếm (Hamming [ n , k , 3 ] {\displaystyle [n,k,3]} , Golay [ 24 , 12 , 8 ] , [ 23 , 12 , 7 ] , [ 12 , 6 , 6 ] {\displaystyle [24,12,8],[23,12,7],[12,6,6]} )
Một điều thường bị bỏ qua là số lượng những hàng xóm kế cận (neighbors) mà một mã ký có thể có. Chúng ta có thể dùng lại ví dụ các đồng xu ở đây. Đầu tiên, chúng ta gộp các đồng xu lại theo các hàng hình chữ nhật. Mỗi một đồng xu có 4 đồng kế cận (và bốn cái ở bốn góc xa hơn). Trong bố cục của hình lục giác, mỗi đồng xu có 6 đồng kế cận. Khi chúng ta tăng số chiều lên, số lượng các đồng kế cận tăng lên một cách nhanh chóng.
Kết quả là số lượng các âm tạp, bên cạch các âm chính, mà máy thu có thể chọn, cũng tăng lên, và do đó mà gây ra lỗi. Đây chính là khuyết điểm căn bản của mã khối, và cũng là khuyết điểm của tất cả các loại mã. Có thể việc gây lỗi trở nên khó khăn hơn, nếu chỉ có một hàng xóm kế cận mà thôi, song con số các hàng xóm kế cận có thể lớn đến độ làm cho chính tổng xác suất lỗi bị ảnh hưởng (total error probability actually suffers).
Mã kết hợp (Convolutional codes) được sử dụng trong các modem dải tần âm (voiceband modems) (V.32, V.17, V.34) và trong các điện thoại di động GSM3, cũng như trong các thiết bị truyền thông của quân đội vũ trang và trong các thiết bị truyền thông với vệ tinh.
Ý định ở đây là làm cho tất cả các ký hiệu mã ký (codeword symbol) trở thành tổng trọng số (weighted sum) của nhiều loại ký hiệu thông điệp trong nhập liệu (various input message symbols). Nó tương tự như toán kết hợp được dùng trong các hệ tuyến tính bất biến (linear time invariant systems) để dùng tìm xuất liệu (output) của một hệ thống, khi chúng ta biết nhập liệu (input) và các đáp ứng xung (impulse response).
Nói chung chúng ta tìm xuất liệu của bộ mã hóa kết hợp hệ (system convolutional encoder), tức sự kết hợp của nhập liệu bit, đối chiếu với trạng thái của bộ mã hóa kết hợp (convolution encoder), hoặc trạng thái của các thanh biến (registers).
Về cơ bản mà nói, mã kết hợp không giúp thêm gì trong việc chống nhiễu hơn một mã khối tương ứng. Trong nhiều trường hợp, chúng nói chung cho chúng ta một phương pháp thực thi đơn giản hơn, hơn hẳn một mã khối có hiệu quả tương ứng (a block code of equal power). Bộ mã hóa thường là một mạch điện đơn giản, có một bộ nhớ (state memory), một vài biện pháp truyền thông tin phản hồi báo tình hình (some feedback logic), thường là các cổng loại trừ XOR (XOR gates). Bộ mã hóa có thể được thực thi trong phần mềm hay phần sụn (firmware).
Thuật toán Viterbi (Viterbi algorithm) là một thuật toán ngắn gọn nhất (optimum algorithm) được dùng để giải mã các mã kết hợp. Hiện có những phương pháp giảm ước giúp vào việc giảm khối lượng tính toán phải làm. Những phương pháp này phần lớn dựa vào việc tìm tuyến đường có khả năng xảy ra cao nhất (most likely paths). Tuy không ngắn gọn, song trong môi trường nhiễu thấp hơn, người ta thường thấy chúng cho những kết quả khả quan. Các bộ điều hành vi xử lý hiện đại (Modern microprocessors) có khả năng thực hiện những thuật toán tìm giảm ước nói trên với tỷ lệ trên 4000 mã ký trong một giây.
Thực đơn
Lý_thuyết_mã_hóaLiên quan
Tài liệu tham khảo
WikiPedia: Lý_thuyết_mã_hóa